How to build a data structure Stack and Queue.
- Tram Ho
Preamble
Hello everyone, today I will share with you how to be able to build two types of data structure stack (stack) and queue (queue) using arrays in C ++;
Normally, in the process of working, I think there must have been many of you who have worked with these two types of data structures. And most of you use Stack, Queue built-in programming languages. So have you ever thought of how Stack and Queue are built? And can you build it yourself? I will help you answer “Yes, absolutely possible”.
So before going into building it, I will go through a bit of basic knowledge about these two types of structure.
1. Introduction to Stack and Queue.
1.1 Stack
Stack, also known as stack, is a type of abstract data structure operating under the principle of “First In First Out” – Last In First Out (LIFO).
The figure above clearly describes the structure of a stack as defined. To make it easier to use, I will take one specific example like this. For example, if you have a bookshelf, if you want to add a new book to the shelf, you can simply place that book on top of the shelf. Or if you want to get a book from the shelf, you can simply get the first book off the shelf. Simple stack is not it! So the operation with the stack is also simple. Here are some basic operations with stacks:
- push: push a test piece into the top of the stack.
- pop: removes the first 1 element from the stack.
- peek: grabs the first element of the stack without deleting it.
- isFull: check if the stack is full.
- isEmpty: check if the stack is empty.
- Note: All stack operations only affect elements at the top of the stack.
OK, I just kept talking about the stack. I’ll have time to write more details or find out for yourself. Now I turn to learn Queue see how it is offline! Let’s go.
1.2 Queue
Queue, also known as queue, is an abstract data structure operating under the principle of “First In First Out” – First In First Out (FIFO).
This figure also describes quite clearly the structure of a queue. However, I want to take a more realistic example for you to easily imagine. For example, when you go to a movie ticket stall, the seller is only 1, and the buyer is very crowded. So you have to wait in line to wait. So, if you queue first, you will be able to buy tickets in advance, whoever comes in later will buy later. (However, the reality is not always the case)
The queue is not something sublime, is it right? So when working with queues also have some basic operations:
- enqueue: add 1 element to the queue.
- dequeue: remove 1 element from the queue.
- peek: get the first element of the queue without deleting it.
- isFull: check if the queue is full.
- isEmpty: check if the queue is empty
Note: All queue operations will affect the beginning and end elements of the queue.
At this point, I have provided you with the most basic knowledge about stacks and queues. Now I will guide you how to build specific of each type like. The first is the stack. Well, in this part of construction, I use C ++ to code, you can use Java or any language you like to follow. I think the construction in other languages is not much different, it’s just the logic. Ahihi (^_^)
2. Building Stack
First I will perform initialization of the stack with the information: top position (top of the stack), stack size
1 2 3 4 5 6 7 | // định nghĩa kích thước của ngăn xếp int size = 100; // tạo 1 biến để xác định vị trí đầu ngăn xếp int top = 0; // khai báo 1 mảng để tạo ngăn xếp int stack[100]; |
Next is the definition of methods corresponding to the operations as above.
- isEmpty : check if the stack is empty
1 2 3 4 | bool isEmpty() { return top == 0 ? true : false; } |
- isFull : check to see if the stack is full
1 2 3 4 | bool isFull() { return top == size ? true : false; } |
- push : put an element at the top of the stack
1 2 3 4 5 6 7 8 9 | void push(int item) { if (isFull()) { cout << "Ngăn xếp đầy rùi má ơi, không push được nữa đâu!" << endl; return; } top++; stack[top] = item; } |
- pop : remove 1 element from the top of the stack
1 2 3 4 5 6 7 8 9 | void pop() { if (isEmpty()) { cout << "Uầy, ngăn xếp rỗng má ơi, có gì đâu mà pop!" return; } stack[top] = 0; top--; } |
- peek: get 1 stack element without deleting it
1 2 3 4 | int peek() { return stack[top]; } |
OK, so you’ve built up the basic operations with the stack already, nothing is bothering you, right? This is the complete program when pairing the above methods together.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | #include <iostream> using namespace std; int size = 10; int top = -1; int stack[10]; bool isEmpty() { return top == -1 ? true : false; } bool isFull() { return top == size ? true : false; } void push(int item) { if (isFull()) { cout << "Ngăn xếp đầy rùi má ơi, không push được nữa đâu!" << endl; return; } top++; stack[top] = item; } void pop() { if (isEmpty()) { cout << "Uầy, ngăn xếp rỗng má ơi, có gì đâu mà pop!" << endl; return; } stack[top] = 0; top--; } int peek() { return stack[top]; } int main() { // gọi các thao tác với stack ở đây return 0; } |
Next will be the queue
3. Building Queue
The first is still the queue initialization, similar to the stack only
1 2 3 4 5 6 7 8 9 | // định nghĩa kích thước của hàng đợi int size = 10; // đánh dấu vị trí đầu hàng đợi int front = 0; // đánh dấu vị trí cuối hàng đợi int rear = -1; // khai báo 1 mảng để tạo hàng đợi int queue[10]; |
Next I will define the operations with the queue.
- isEmpty (): check if the queue is empty
1 2 3 4 | bool isEmpty() { return (front < 0 || front > rear) ? true : false; } |
- isFull (): check if the queue is full.
1 2 3 4 | bool isFull() { return rear == size - 1 ? true : false; } |
- enqueue: add 1 element to the queue.
1 2 3 4 5 6 7 8 9 | void enqueue(int item) { if (isFull()) { cout << "Hàng đợi đầy rùi má ơi, không enqueue được nữa đâu!" << endl; return; } rear++; queue[rear] = item; } |
- dequeue (): remove 1 element from the queue.
1 2 3 4 5 6 7 8 9 | void dequeue() { if (isEmpty()) { cout << "Uầy, hàng đợi rỗng má ơi, có gì đâu mà dequeue!" << endl; return; } queue[front] = 0; front++; } |
- peek (): takes the first element of the queue without deleting it.
1 2 3 4 | int peek() { return queue[front]; } |
Yeh, so it’s done building queue operations, guys, the rest of the work is to code together. This is the complete program after pairing the methods.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | #include <iostream> using namespace std; int size = 10; int front = 0; int rear = -1; int queue[10]; bool isEmpty() { return (front < 0 || front > rear) ? true : false; } bool isFull() { return rear == size - 1 ? true : false; } void enqueue(int item) { if (isFull()) { cout << "Hàng đợi đầy rùi má ơi, không enqueue được nữa đâu!" << endl; return; } rear++; queue[rear] = item; } void dequeue() { if (isEmpty()) { cout << "Uầy, hàng đợi rỗng má ơi, có gì đâu mà dequeue!" << endl; return; } queue[front] = 0; front++; } int peek() { return queue[front]; } int main() { // gọi các thao tác với queue ở đây return 0; } |
Conclude
Above, my share about Stack and Queue. As I said at the beginning, in reality when you go to work, you rarely have to rebuild these types of data structures yourself. Because most of them are already built in programming languages. However, when using these types of data structures, you should also know a little bit about it better. I hope through this article, you will grasp the basic knowledge such as how to operate, manipulate and how to build these two types of structures. My article is using arrays in C ++ to install. You absolutely can use other languages such as java, c # … and other structures such as: linked lists, … to install as you like. Good luck. In the process of writing articles, it is unavoidable shortcomings, I hope to get feedback from you to make the article better. Thanks all!
Source : Viblo