Concept of Stack and Queue in Data Structure
- February 6, 2018
- Posted by: admin
- Category: Computer & IT
Two of the more common data objects found in computer algorithms are stacks and queues. stack queue
Stacks are data structures, which maintain the order of last-in, first-out (LIFO)
Queues are data structures, which maintain the order of first-in, first-out (FIFO)
***Stack: A stack is a storage device that stores information in such a way that the item stored last is the first item retrieved. A stack is an ordered list in which all insertions and deletions are made at one end, called the top.
Stack Pointer: the register that holds the address for the stack is called a stack pointer (SP)coz its value always points at the top item in the stack.
Operations of a Stack
The operations of a stack can be matched to the stack of trays. The last tray placed on top of the stack is the first to be taken off. The two operations; performed on a stack are insertion and deletion of items.Insertion and deletion, both acted upon at one end of the list (called the top).
Insert element with value X at top of stack.
Remove top element of stack
These operations are simulated by incrementing or decrementing the stack pointer register.
The PUSH operation is implemented with the following sequence of micro operations:
SPß SP+1 (increment stack pointer)
M [SP]ßDR (write item on top of the stack)
If (SP=0) then (FULLß1) (check if stack is full)
EMPTYß0 (Mark the stack not empty)
The POP operation is implemented with the following sequence of micro operations:
DRß M [SP] (Read item from the top of stack)
SPßSP-1 (Decrement stack pointer)
If (SP=0) then (EMPTYß1) (check if stack is empty)
FULLß0 (Mark the stack is not full)
Stack as an Abstract Data Type
Here is a more formal definition of the stack ADT: A stack is a data structure containing zero or more elements, on which the following operations can be performed:
Create a new, empty stack object.
Determine whether the stack is empty; return true if it is and false if it is not.
Push and Pop I have defined earlier
Return the element at the top of the stack (without removing it from the stack). (This operation, too, can be performed only if the stack is not empty.)
This abstract data type definition says nothing about how we will program the various stack operations; rather, it tells us how stacks can be used. We can infer some limitations on how we can use the data. A stack organization is very effective for evaluating arithmetic expressions.
***Queue: A queue is an ordered list in which all insertions take place at one end, the rear, while all deletions take place at the other end, the front. Like a line of people waiting for some service, a queue acquires new elements at one end (the rear of the queue) and releases old elements at the other (the front). Queues are more difficult to implement than stacks, because action happens at both ends.
Queue as an Abstract Data Type
Following is the abstract data type definition for queues, with the conventional names for the operations:
Create a new, empty queue object.
Determine whether the queue is empty; return true if it is and false if it is not.
Add a new element at the rear of a queue.
Remove an element from the front of the queue and return it. (This operation cannot be performed if the queue is empty.)
Return the element at the front of the queue (without removing it from the queue). (Again, this operation cannot be performed if the queue is empty.)
Types of Queues : some of them are given below:
Circular Queues :Circular queues let us reuse empty space.
Double-ended queues – These are data structures which support both push and pop and enqueue/dequeue operations.
Priority Queues(heaps) – Supports insertions and “remove minimum” operations which useful in simulations to maintain a queue of time events.
this is what the brief account in context of stack and queries …
“Polish Notation and Stack Evaluation”.
There are some terminologies could help us a lot while writing down an essay over Stacks and Ques in exams like; infix, Polish or Parenthesis-free notation.
Infix is the ordinary notation for writing expressions, where operators separate arguments.
while in the case of Polish notation which is really useful for stack oriented evaluation operater comes after the arguments. for example,
3, 5, +(Polish notation) => 3+5 (infix notation) and
10 , 6, 9, *, + (Polish notation) => 10+(6*9) (infix notation)etc
A polish expression could better be evaluated by such algorithm using two stacks. A polish stack will contain polish expression and the evaluation stack stores the intemediate values during execution.
Lets evaluate the polish expressions now. We will use A, B and C to hold data. What will happen when the program will execute. The following actions will be done:
1. If the polish stack is empty, halt with the top e. stack as the answer.
2. If stack is not empty, pop the polish stack into A.
3. If A is a value then push A onto the e. stack.
4. If A is an operator then pop the e. stack twice, first into C and then into B. Then do the computation of B and C and then operate them on by A and push the result into e. stack. Go to step 1.
That was a curt introduction to the evaluation of Stacks and what are polish notations
Back to Blogs