Where does the top variable point when a stack is implemented with an array?
Array implementation of StackIn array implementation, the stack is formed by using the array. All the operations regarding the stack are performed using arrays. Lets see how each operation can be implemented on the stack using array data structure. Show
Adding an element onto the stack (push operation)Adding an element into the top of the stack is referred to as push operation. Push operation involves following two steps.
Stack is overflown when we try to insert an element into a completely filled stack therefore, our main function must always avoid stack overflow condition. Algorithm: Time Complexity : o(1) implementation of push algorithm in C languageDeletion of an element from a stack (Pop operation)Deletion of an element from the top of the stack is called pop operation. The value of the variable top will be incremented by 1 whenever an item is deleted from the stack. The top most element of the stack is stored in an another variable and then the top is decremented by 1. the operation returns the deleted value that was stored in another variable as the result. The underflow condition occurs when we try to delete an element from an already empty stack. Algorithm : Time Complexity : o(1) Implementation of POP algorithm using C languageVisiting each element of the stack (Peek operation)Peek operation involves returning the element which is present at the top of the stack without deleting it. Underflow condition can occur if we try to return the top element in an already empty stack. Algorithm : PEEK (STACK, TOP) Time complexity: o(n) Implementation of Peek algorithm in C languageC program Java Program C# Program Next TopicDS Linked List Implementation of Stack ← prev next → Growable array based stackWe all know about Stacks also known as Last-In-First-Out(LIFO) structures. Stack primarily has two main operation namely push and pop, where push inserts an element at top and pop removes an element from top of the stack. But what if a stack can grow as more elements are inserted or more elements are going to be inserted in future. Remember, we are talking about array based Stack. Growable Stack is the concept of allocating more memory such that “stack full” condition does not arises easily. There are two operation on growable stack: Recommended: Please try your approach on {IDE} first, before moving on to the solution. C++
Java
Python3
C#
Javascript
. Output: Stack: 1 2 3 4 Stack: 1 2 3 4 5 6 Stack: 1 2 3 4 5 6 7 8 Stack: 1 2 3 4 5 6 7 8 9
Article Tags :
Arrays Stack
Practice Tags :
Arrays Stack IntroductionHave you always wanted to learn about stacks? Do you also want to know how to implement it in code or a way to visualize it? Then, you are at the right place. This article aims to provide you with in-depth knowledge about stack implementation in one of the easiest and systematic ways. Before discussing more implementation, let’s brush up on our knowledge about stacks. So, What are stacks? No, I don’t want you to think of it as a coding question; just imagine how a stack looks in the practical world. See this image: So, we have five disks stacked together, as shown above. The numbers represent the order in which we place them one by one on top of each other. So, this is what a stack looks like. Stack is a linear data structure that allows the most recently added elements to be removed first and this feature is more popularly known as LIFO ( last in, first out). So, both the insertion and deletion of elements happen only from one end, i.e. from the top of the stack. The main functions of the stack include –
Now that you are confident about the foundation, let’s think about how to mimic this stack in our code, i.e. how to implement it. Maybe you should wonder –
Non-essential operationsEditIn many implementations, a stack has more operations than the essential "push" and "pop" operations. An example of a non-essential operation is "top of stack", or "peek", which observes the top element without removing it from the stack.[17] This could be done with a "pop" followed by a "push" to return the same data to the stack, so it is not considered an essential operation. If the stack is empty, an underflow condition will occur upon execution of either the "stack top" or "pop" operations. Additionally, many implementations provide a check if the stack is empty and one that returns its size. Software stacksEditImplementationEditA stack can be easily implemented either through an array or a linked list. What identifies the data structure as a stack, in either case, is not the implementation but the interface: the user is only allowed to pop or push items onto the array or linked list, with few other helper operations. The following will demonstrate both implementations, using pseudocode. ArrayEditAn array can be used to implement a (bounded) stack, as follows. The first element, usually at the zero offset, is the bottom, resulting in array[0] being the first element pushed onto the stack and the last element popped off. The program must keep track of the size (length) of the stack, using a variable top that records the number of items pushed so far, therefore pointing to the place in the array where the next element is to be inserted (assuming a zero-based index convention). Thus, the stack itself can be effectively implemented as a three-element structure: structure stack: maxsize: integer top: integer items: array of item procedure initialize(stk: stack, size: integer): stk.items ← new array of size items, initially empty stk.maxsize ← size stk.top ← 0The push operation adds an element and increments the top index, after checking for overflow: procedure push(stk: stack, x: item): if stk.top = stk.maxsize: report overflow error else: stk.items[stk.top] ← x stk.top ← stk.top + 1Similarly, pop decrements the top index after checking for underflow, and returns the item that was previously the top one: procedure pop(stk: stack): if stk.top = 0: report underflow error else: stk.top ← stk.top − 1 r ← stk.items[stk.top] return rUsing a dynamic array, it is possible to implement a stack that can grow or shrink as much as needed. The size of the stack is simply the size of the dynamic array, which is a very efficient implementation of a stack since adding items to or removing items from the end of a dynamic array requires amortized O(1) time. Linked listEditAnother option for implementing stacks is to use a singly linked list. A stack is then a pointer to the "head" of the list, with perhaps a counter to keep track of the size of the list: structure frame: data: item next: frame or nil structure stack: head: frame or nil size: integer procedure initialize(stk: stack): stk.head ← nil stk.size ← 0Pushing and popping items happens at the head of the list; overflow is not possible in this implementation (unless memory is exhausted): procedure push(stk: stack, x: item): newhead ← new frame newhead.data ← x newhead.next ← stk.head stk.head ← newhead stk.size ← stk.size + 1 procedure pop(stk: stack): if stk.head = nil: report underflow error r ← stk.head.data stk.head ← stk.head.next stk.size ← stk.size - 1 return rStacks and programming languagesEditSome languages, such as Perl, LISP, JavaScript and Python, make the stack operations push and pop available on their standard list/array types. Some languages, notably those in the Forth family (including PostScript), are designed around language-defined stacks that are directly visible to and manipulated by the programmer. The following is an example of manipulating a stack in Common Lisp (">" is the Lisp interpreter's prompt; lines not starting with ">" are the interpreter's responses to expressions): > (setf stack (list 'a 'b 'c)) ;; set the variable "stack"
(A B C)
> (pop stack) ;; get top (leftmost) element, should modify the stack
A
> stack ;; check the value of stack
(B C)
> (push 'new stack) ;; push a new top onto the stack
(NEW B C)
Several of the C++ Standard Library container types have push_back and pop_back operations with LIFO semantics; additionally, the stack template class adapts existing containers to provide a restricted API with only push/pop operations. PHP has an SplStack class. Java's library contains a Stack class that is a specialization of Vector. Following is an example program in Java language, using that class. import java.util.Stack;
class StackDemo {
public static void main(String[]args) {
Stack stack = new Stack();
stack.push("A"); // Insert "A" in the stack
stack.push("B"); // Insert "B" in the stack
stack.push("C"); // Insert "C" in the stack
stack.push("D"); // Insert "D" in the stack
System.out.println(stack.peek()); // Prints the top of the stack ("D")
stack.pop(); // removing the top ("D")
stack.pop(); // removing the next top ("C")
}
}
|
