Stack in data structure

12 Key excerpts on "Stack in data structure"

• 

  eBook - ePub

  Data Structures and Program Design Using Python

  A Self-Teaching Introduction

  • D. Malhotra, N. Malhotra(Authors)
  • 2020(Publication Date)
  • Mercury Learning and Information

    (Publisher)

  CHAPTER 7

  STACKS

  7.1 INTRODUCTION

  A stack is an important data structure that is widely used in many computer applications. A stack can be visualized with familiar examples from our everyday lives. A very simple illustration of a stack is a pile of books, where one book is placed on top of another as shown in Figure 7.1 . When we want to remove a book, we remove the topmost book first. Hence, we can add or remove an element (i.e., a book) only at or from one position, that is, the topmost position. In a stack, the element in the last position is served first. Thus, a stack can be described as a LIFO (Last In, First Out) data structure; that is, the element that is inserted last will be the first one to be taken out.

  FIGURE 7.1 A stack of books

  7.2 DEFINITION OF A STACK

  A stack is a linear collection of data elements in that the element inserted last will be the element taken out first (i.e., a stack is a LIFO data structure). The stack is an abstract data structure, somewhat similar to queues. Unlike queues, a stack is open only on one end. A stack is a linear data structure in that the insertion and deletion of elements are done only from the end called TOP. One end is always closed, and the other end is used to insert and remove data.

  Stacks can be implemented by using arrays or linked lists. We discuss the implementation of stacks using arrays and linked lists in this section.

  FIGURE 7.2 Representation of a stack

  Practical Application:

  1. A real-life example of a stack is a pile of dishes, where one dish is placed on top of another. Now, when we want to remove a dish, we remove the topmost dish first.

  2.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Data Structures and Program Design Using C++

  • D. Malhotra, N. Malhotra(Authors)
  • 2019(Publication Date)
  • Mercury Learning and Information

    (Publisher)

  7

  STACKS

  In This Chapter

  • Introduction

  • Definitions of a stack

  • Overflow and underflow in stacks

  • Operations on stacks

  • Implementation of stacks

  • Applications of stacks

  • Summary

  • Exercises

  7.1Introduction

  A stack is an important data structure which is widely used in many computer applications. A stack can be visualized with many familiar examples from our day-to-day lives. A very simple illustration of a stack is a pile of books where one book is placed on top of another as in Figure 7.1 . When we want to remove a book, we remove the topmost book first. Hence, we can add or remove an element (i.e., book) only at or from one position, which is the topmost position. There are many other daily life examples in which we can see how a stack is implemented. We observe that whenever we talk about a stack, we see that the element at the last position will be served first. Thus, a stack can be described as a LIFO (last in, first out) data structure; that is, the element which is inserted last will be the first one to be taken out. Now, let us discuss stacks in detail.

  FIGURE 7.1 Stack of books.

  7.2Definition of a Stack

  A stack is a linear collection of data elements in which the element inserted last will be the element taken out first (i.e., a stack is a LIFO data structure). The stack is an abstract data structure, somewhat similar to queues. Unlike queues, a stack is open only on one end. The stack is a linear data structure in which the insertion and deletion of elements is done only from the end called TOP . One end is always closed, and the other end is used to insert and remove data.

  Stacks can be implemented by using arrays or linked lists. We will discuss the implementation of stacks using arrays and linked lists in this section.

  FIGURE 7.2 Representation of a stack.

  Practical Application: 1.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Data Structures and Program Design Using Java

  A Self-Teaching Introduction

  • D. Malhotra, N. Malhotra(Authors)
  • 2020(Publication Date)
  • Mercury Learning and Information

    (Publisher)

  7

  STACKS

  7.1  Introduction

  A stack is an important data structure which is widely used in many computer applications. A stack can be visualized with many familiar examples from our day-to-day lives. A very simple illustration of a stack is a pile of books where one book is placed on top of another as in Figure 7.1 .When we want to remove a book, we remove the topmost book first. Hence, we can add or remove an element (i.e., book) only at or from one position, which is the topmost position. There are many other daily life examples in which we can see how a stack is implemented. We observe that whenever we talk about a stack, we see that the element at the last position will be served first. Thus, a stack can be described as a LIFO (last in, first out) data structure; that is, the element which is inserted last will be the first one to be taken out. Now, let us discuss stacks in detail.

  Figure 7.1. Stack of books.

  7.2  Definition of a Stack

  A stack is a linear collection of data elements in which the element inserted last will be the element taken out first (i.e., a stack is a LIFO data structure).The stack is an abstract data structure, somewhat similar to queues. Unlike queues, a stack is open only on one end. The stack is a linear data structure in which the insertion and deletion of elements is done only from the end called TOP. One end is always closed, and the other end is used to insert and remove data.

  Stacks can be implemented by using arrays or linked lists. We will discuss the implementation of stacks using arrays and linked lists in this section.

  Figure 7.2. Representation of a stack.

  Practical Application

  1. A real-life example of a stack is a pile of dishes where one dish is placed on top of another. Now, when we want to remove a dish, we remove the topmost dish first.
  2. Another real-life example of a stack is a pile of discs where one disc is placed on top of another. Now, when we want to remove a disc, we remove the topmost disc first.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Python Data Structures Pocket Primer

  • Oswald Campesato(Author)
  • 2022(Publication Date)
  • Mercury Learning and Information

    (Publisher)

  This concludes the portion of the chapter pertaining to queues. The remainder of this chapter discusses the stack data structure, which is based on a LIFO structure instead of a FIFO structure of a queue.

  WHAT IS A STACK?

  In general terms, a stack consists of a collection of objects that follow the LIFO (last-in-first-out) principle. By contrast, a queue follows the FIFO (first-in-first-out) principle.

  As a simple example, consider an elevator that has one entrance: the last person who enters the elevator is the first person who exits the elevator. Thus, the order in which people exit an elevator is the reverse of the order in which people enter an elevator.

  Another analogy that might help you understand the concept of a stack is a stack of plates in a cafeteria:

  • A plate can be added to the top of the stack if the stack is not full.
  • A plate can be removed from the stack if the stack is not empty.

  Based on the preceding observations, a stack has a maximum size MAX and a minimum size of 0.

  Use Cases for Stacks

  The following list contains use applications and use cases for stack-based data structures:

  • recursion
  • keeping track of function calls
  • evaluation of expressions
  • reversing characters
  • servicing hardware interrupts
  • solving combinatorial problems using backtracking

  Operations With Stacks

  Earlier in this chapter you saw Python functions to perform operations on queues; in an analogous fashion, we can define a stack in terms of the following methods:

  • isEmpty() returns True if the stack is empty
  • isFull() returns True if the stack is full
  • stackSize() returns the number of elements in the stack
  • push(item) adds an element to the "top" of the stack if the stack is not full
  • pop() removes the top-most element of the stack if the stack is not empty

  In order to ensure that there is no overflow (too big) or underflow (too small), we must always invoke isEmpty() before popping an item from the stack and always invoke isFull()

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Data Structure Using C

  Theory and Program

  • Ahmad Talha Siddiqui, Shoeb Ahad Siddiqui(Authors)
  • 2023(Publication Date)
  • CRC Press

    (Publisher)

  4 Stack

  4.1 Introduction

  Stack is a specialized data storage structure (Abstract data type). It has two main functions-push and pop. Insertion in a stack is done using push function and removal from a stack is done using pop function. Stack allows access to only the last element inserted hence, an item can be inserted or removed from the stack from one end called the top of the stack. It is therefore, also called Last-In-First-Out (LIFO) list. Stack has three properties:

  1. Capacity stands for the maximum number of elements stack can hold.
  2. Size stands for the current size of the stack.
  3. Elements are the array of elements.

  The Linear data structure such as array and a linked list allows us to delete and insert an element at any place in the list, either at the beginning or at the end or even in the middle. However, sometimes it is required to permit the addition or deletion of elements only at one end. That is either at the beginning or at the end. Stack and queue are two types of data structures in which the addition or deletion of an element is done at end, rather than in the middle. A stack is a linear data structure in which all insertions and deletions are made at one end, called the top of the stack. It is very useful in many applicationssuch as:

  • We see stack (pile) of plates in restaurant, stack of books in bookshop.
  • Even a packet of papers is also a stack of paper-sheet. A book is also astack of written papers.
  • When anybody takes a plate from a stack of plates, he takes it from the top.

  Definition

  A stack is an ordered collection of homogeneous data elements where the insertion and deletion operations occur at only one end. This end is often known as top of the stack. Here, the last element inserted will be top of the stack. Since deletion is done from the same end, last element inserted will be the first element to be removed out from the stack and so on. That is why the stack is also called Last-in-First-Out (LIFO).

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Quick Reference to Data Structures and Computer Algorithms, A

  An Insight on the Beauty of Blockchain

  • Divya Joseph(Author)
  • 2019(Publication Date)
  • BPB Publications

    (Publisher)

  HAPTER 3

  Stacks and Queues

  3.1 Definition and Concepts

  It may be possible that there is a need for a data structure which takes operation on only one end. i.e., beginning or end of the list. In linked list and arrays, we can perform operations at any place of the list. Stack and Queue, are data structures which fulfill the requirements to perform operation on only at one end.

  3.2 Stack

  A stack is a special purpose data structure, containing a list, where data are arranged in order, in which all operations such as insertions and deletions are carried out in only one place, called the TOP of the stack.

  Given a stack, S = (a1 , …., an ) then we say that a1 is the bottom most element and element ai is on top of element ai -1, 1 < i ≤ n.

  Definition: A stack is a collection of similar data, which is having some order, where all the operations like insertion and deletion, carried out, only at one end.

  Stack is also a linear data structure, the insertion and deletion operations in case of stack is specially termed as PUSH and POP respectively, and the position of the stack where such operations are carried out, is known as the TOP of the stack. An element in a stack is commonly termed as an ITEM. The SIZE of a stack defines the maximum number of elements that a stack can hold at once (figure 3.1).

  Figure 3.1 Schematic diagram of a stack

  In stack, the element, which is inserted the last, is the first to be removed from the stack. For this reason, stacks are also known as Last In First Out(LIFO) lists.

  One natural example of stacks which arises in Computer Programming is the processing of subroutine calls and their returns. Suppose we have a main procedure and 3 subroutines as follows:

  Figure 3.2 Sequence of subroutines being called

  The MAIN program calls subroutine X. On completion of X, execution of MAIN will resume at location b. The address b is passed to X, which saves it in some location for later procession. X then invokes Y, which in turn calls Z. In every case the calling procedure passes the return address to the called procedure. If we examine the memory which Z is computing there will be an implicit stack which looks like (a, b, c, d).

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Hands-On Data Structures and Algorithms with Python

  • Dr. Basant Agarwal(Author)
  • 2022(Publication Date)
  • Packt Publishing

    (Publisher)

  A stack is a data structure that stores data, similar to a stack of plates in a kitchen. You can put a plate on the top of the stack, and when you need a plate, you take it from the top of the stack. The last plate that was added to the stack will be the first to be picked up from the stack: Figure 5.1: Example of a stack

  The preceding diagram depicts a stack of plates. Adding a plate to the pile is only possible by leaving that plate on top of the pile. To remove a plate from the pile of plates means to remove the plate that is on top of the pile.

  A stack is a data structure that stores the data in a specific order similar to arrays and linked lists, with several constraints:

  • Data elements in a stack can only be inserted at the end (push operation)
  • Data elements in a stack can only be deleted from the end (pop operation)
  • Only the last data element can be read from the stack (peek operation)

  A stack data structure allows us to store and read data from one end, and the element which is added last is picked up first. Thus, a stack is a last in first out (LIFO) structure, or last in last out (LILO ).

  There are two primary operations performed on stacks – push and pop . When an element is added to the top of the stack, it is called a push operation, and when an element is to be picked up (that is, removed) from the top of the stack, it is called a pop operation. Another operation is peek , in which the top element of the stack can be viewed without removing it from the stack. All the operations in the stack are performed through a pointer, which is generally named top . All these operations are shown in Figure 5.2

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Java Basics Using ChatGPT/GPT-4

  • Oswald Campesato(Author)
  • 2023(Publication Date)
  • Mercury Learning and Information

    (Publisher)

  circular queue is a queue whose “head” is the same as its “tail.” A priority queue is a queue in which elements are assigned a numeric priority. A dequeue is a queue in which elements can be added as well as removed from both ends of the queue. Search online for code samples that implement these types of queues.

  This concludes the portion of the chapter pertaining to queues. The remainder of this chapter discusses the stack data structure, which is based on a LIFO (last-in-first-out) structure instead of a FIFO structure of a queue.

  WHAT IS A STACK?

  In general terms, a stack consists of a collection of objects following the LIFO principle. By contrast, a stack follows the LIFO principle.

  As a simple example, consider an elevator that has one entrance: the last person who enters the elevator is the first person who exits the elevator. Thus, the order in which people exit an elevator is the reverse of the order in which people enter an elevator.

  Another analogy that might help you understand the concept of a stack is the stack of plates in a cafeteria:

  1. A plate can be added to the top of the stack if the stack is not full.

  2. A plate can be removed from the stack if the stack is not empty.

  Based on the preceding observations, a stack has a maximum size MAX and a minimum size of 0.

  Use Cases for Stacks

  The following list contains use applications and use cases for stack-based data structures:

  ■ recursion

  ■ keeping track of function calls

  ■ evaluation of expressions

  ■ reversing characters

  ■ servicing hardware interrupts

  ■ solving combinatorial problems using backtracking

  Operations With Stacks

  Earlier in this chapter you saw Java methods to perform operations on queues; in an analogous fashion, we can define a stack in terms of the following methods:

  ■ isEmpty() returns True if the stack is empty

  ■ isFull() returns True if the stack is full

  ■ stackSize() returns the number of elements in the stack

  ■ push(item)

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Data structures based on linear relations

  • Xingni Zhou, Zhiyuan Ren, Yanzhuo Ma, Kai Fan, Xiang Ji(Authors)
  • 2020(Publication Date)
  • De Gruyter

    (Publisher)

  3  Linear list with restricted operations – stack and queue

  Main Contents

  • The logic structure definition of stack
  • The storage structure of stack and the implementation of its operations
  • The logic structure definition of queue
  • The storage structure of queue and the implementation of its operations

  Learning Aims

  • Comprehend the features and operation methods of stacks and queues
  • Correctly choose them in actual applications

  3.1  Stack – a linear list managed in a first-in–last-out manner

  The notion of “stack” in data structures comes from the meaning of “stack” in daily lives, which has the characteristic of “first-in–last-out.” See Fig. 3.1 . For things that can be stacked together, we always put the ones below first, and then the ones above, and the order of retrieval is exactly opposite to the order of storage. We can see the meaning of Stack in data structures via the algorithmic implementations of some actual problems.

  Fig. 3.1: Stack in daily lives.

  3.1.1  Introduction to the operation pattern of stack

  3.1.1.1  Introduction to stack 1 – erroneous operation in Word

  Word is a commonly used word editing software. If there is some erroneous operation during usage, for example, deleting the wrong content, will you be worried? People familiar with Word will usually say “it doesn’t matter,” since you can use “undo” tool to restore the content erroneously deleted. The “undo” tool can undo the previous operation. Actually, editing software nowadays all has “undo” functionality. Note that the order of “undo” operations is exactly the opposite of normal operations, as shown in Fig. 3.2

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Essential Algorithms

  A Practical Approach to Computer Algorithms Using Python and C#

  • Rod Stephens(Author)
  • 2019(Publication Date)
  • Wiley

    (Publisher)

  CHAPTER 5 Stacks and Queues

  Stacks and queues are relatively simple data structures that store objects in either first-in-first-out order or last-in-first-out order. They expand as needed to hold additional items, much like linked lists can, as described in Chapter 3 , “Linked Lists.” In fact, you can use linked lists to implement stacks and queues.

  You can also use stacks and queues to model analogous real-world scenarios, such as service lines at a bank or supermarket. Usually, however, they are used to store objects for later processing by other algorithms, such as shortest-path algorithms.

  This chapter describes stacks and queues. It explains what they are, explains stack and queue terminology, and describes the methods that you can use to implement them.

  Stacks

  A stack is a data structure where items are added and removed in last-in-first-out order. Because of this last-in-first-out (LIFO, usually pronounced “life-oh”) behavior, stacks are sometimes called LIFO lists or LIFOs.

  A stack is similar to a pile of books on a desk. You can add a book to the top of the pile or remove the top book from the pile, but you can't pull a book out of the middle or bottom of the pile without making the whole thing topple over.

  A stack is also similar to a spring-loaded stack of plates at a cafeteria. If you add plates to the stack, the spring compresses so that the top plate is even with the countertop. If you remove a plate, the spring expands so that the plate that is now on top is still even with the countertop. Figure 5.1 shows this kind of stack.

  Figure 5.1

  :

  A stack is similar to a stack of plates at a cafeteria.

  Because this kind of stack pushes plates down into the counter, this data structure is also sometimes called a pushdown stack. Adding an object to a stack is called pushing the object onto the stack, and removing an object from the stack is called popping the object off of the stack. A stack class typically provides Push and Pop

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Data Structures in Java

  • Oswald Campesato(Author)
  • 2023(Publication Date)
  • Mercury Learning and Information

    (Publisher)

  circular queue is a queue whose “head” is the same as its “tail.” A priority queue is a queue in which elements are assigned a numeric priority. A dequeue is a queue in which elements can be added as well as removed from both ends of the queue. Search online for code samples that implement these types of queues.

  This concludes the portion of the chapter pertaining to queues. The remainder of this chapter discusses the stack data structure, which is based on a LIFO structure instead of a FIFO structure of a queue.

  WHAT IS A STACK?

  In general terms, a stack consists of a collection of objects that follow the LIFO (last-in-first-out) principle. By contrast, a queue follows the FIFO (first-in-first-out) principle.

  As a simple example, consider an elevator that has one entrance: the last person who enters the elevator is the first person who exits the elevator. Thus, the order in which people exit an elevator is the reverse of the order in which people enter an elevator.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  The Complete Coding Interview Guide in Java

  An effective guide for aspiring Java developers to ace their programming interviews

  • Anghel Leonard(Author)
  • 2020(Publication Date)
  • Packt Publishing

    (Publisher)

  MyStack .

  Queues in a nutshell

  A queue is a linear data structure that uses the First-In-First-Out (FIFO ) principle. Think of people standing in a queue to buy stuff. You can also imagine ants that are walking in a queue formation.

  So, technically speaking, the elements are removed from the queue in the same order that they are added. In a queue, the elements added at one end referred to as the rear (this operation is known as the enqueue operation) and removed from the other end referred to as the front (this operation is known as the dequeue or poll operation).

  The common operations in a queue are as follows:

  • enqueue(E e) : Adds an element to the rear of the queue
  • E dequeue() : Removes and returns the element from the front of the queue
  • E peek() : Returns (but doesn't remove) the element from the front of the queue
  • boolean isEmpty() : Returns true if the queue is empty
  • int size() : Returns the size of the queue
  • boolean isFull() : Returns true if the queue is full

  Unlike an array, a queue does not provide access to the n th element in constant time. However, it does provide constant time for adding and removing elements. A queue can be implemented on top of an array or even on top of a linked list or a stack (which is built on top of an array or a linked list). The implementation used here is based on an array and is named MyQueue

  Sign up to read

  Learn more about book