Stack

0 phút đọc

Quick reference

Worst Case
space O(n)
push O(1)
pop O(1)
peek O(1)

A stack stores items in a last-in, first-out (LIFO) order.

Picture a pile of dirty plates in your sink. As you add more plates, you bury the old ones further down. When you take a plate off the top to wash it, you're taking the last plate you put in. "Last in, first out."

Strengths

  • Fast operations. All stack operations take $$O(1)$$ time.

Uses

  • The call stack is a stack that tracks function calls in a program. When a function returns, which function do we "pop" back to? The last one that "pushed" a function call.
  • Depth-first search uses a stack (sometimes the call stack) to keep track of which nodes to visit next.
  • String parsing—stacks turn out to be useful for several types of string parsing

Implementation

You can implement a stack with either a linked list or a dynamic array—they both work pretty well:

Stack Push Stack Pop
Linked Lists insert at head remove at head
Dynamic Arrays append remove last element

Java comes with a built-in stack implementation instead.

The stack implementation has a few big drawbacks: it doesn't have an interface and it extends the Vector class, which has thread synchronization overhead.

Bình luận

Chưa có bình luận nào

Chưa có bình luận nào

Avatar TechMely Team
Được viết bởi

TechMely Team

Lòng tin cũng giống như một tờ giấy, khi đã nhàu nát sẽ không bao giờ phẳng phiu được.
Khoá học javascript từ cơ bản đến chuyên sâuYoutube Techmely