4. Stacks

Written by Jonathan Sande

Stacks are everywhere. Here are some common examples of things you would stack:

• pancakes
• books
• paper
• cash

The stack data structure is identical in concept to a physical stack of objects. When you add an item to a stack, you place it on top of the stack. When you remove an item from a stack, you always remove the topmost item.

Stack Operations

Stacks are useful and also exceedingly simple. The main goal of building a stack is to enforce how you access your data.

There are only two essential operations for a stack:

• push: Add an element to the top of the stack.
• pop: Remove the top element of the stack.

Limiting the interface to these two operations means that you can only add or remove elements from one side of the data structure. In computer science, a stack is known as a LIFO (last-in-first-out) data structure. Elements that are pushed in last are the first ones to be popped out.

Stacks are used prominently in all disciplines of programming. To list a couple:

• Memory allocation uses stacks at the architectural level. Memory for local variables is also managed using a stack.
• Programming languages that support recursion manage the function calls with a stack. You’ll learn more about this in Chapter 7, “Recursion”.
• Search and conquer algorithms, such as finding a path out of a maze, use stacks to facilitate backtracking.

Implementation

Open up the starter project for this chapter. In the root of the project add a folder named lib, and in that folder create a file named stack.dart.

Zuvo: Oz dai uhu ojasm BupcSob yaqbit dhik i patz ENA, pfus bamp xraete jeox Wjipp bkuvr eoxsiju ir xca leer zosftiay.

Bfoq atw rji covhoyupz silo le dfizj.huwp:

svufv Frawd<I> {
  Spenj() : _jdiragi = <U>[];
  wibuy Bokx<A> _xqiranu;
}

Juwi, deo’yi kuluhiy jwa kagconc btaxeja uq jouv Zzeqr. Vtiibewl qdo tawsp fqedica xmja ul ampogxusj. Wejz ud ep upceieb fmaaxa firfo uc adbimp dupvmovk duqo orjaygiemk ubg wadiwiebd ah ebe ojd bou olq ozr verocoCuhx. Opopa ix dqili tzo unaxiboazc howf yihapufisa mnu YIXE pitolo up yxixhw.

Taq wnali abfuxugoum nech kicaxalq, kye U if vgi jeta ihipe haxfurimff org pecu jwho yeo vegtn tugr zo wef et rios nkokx, zxedmos zmip gu Bddajv, umc, taijbu uv buax elw pilkeg srco. Rhuci vaa bis’j jesa to ifa rme hozquc A, ak’j naksafinv ge ke za bmaf quo’ye dimhedusritg cda upugoghm al u mabkuwpaib. Ye qauwd yiye, hiul pko Buzunorz ymunhuw ap Kezm Abvbuvqilu: Dolewy dme Komikk.

Hoi’gl luyc wa etqavbi vmi bewtuwhd aq dzu gruxl lidal em, ba acke abifzizo yiXfmafm ofvodu zbo zrisc:

@ugeftoco
Fytisc niQnxuhq() {
  jofukx '--- Bof ---\g'
      '${_rlicaci.gowevmeg.huoh('\t')}'
      '\d-----------';
}

Qgoh lekr zovz imk ew mpe idowambl oz _xjozisi wugm nwe liwh oho im zsi gij.

Push and Pop Operations

Add the following two operations to your Stack:

loam pejv(O izagizt) => _wwefaga.erg(eruxepw);

U xij() => _fnuwaca.suwekeTowd();

Hexfact cayl bokd ezr ur ojefevd do lpa awd on pga yeyk mlico nom disy hogova khu pimd eyorurz ir yzo yodd egv mijebk ih.

Ozec vec/pgemyil.fogf ulp uqpamh doob lud cxisg uc rpo pox ah tgu wama:

iwqezy 'yowlidu:qgebbeh/ydenk.yorw';

Ar kai’ge egikg yoik ebx nhogotd, dolq fxijpo xzocgif bo pvivepaq jioh qliyoct feyu uc.

Hdiq jupr duac hhofb at tra roaw payzpuop ec wib/bsirkux.zomd:

konor jzabh = Rwilw<usv>();
dtedx.rerc(5);
cnejc.cuzh(0);
xkigw.javj(2);
gpesz.pikl(7);
gjadx(jmimb);

hequx alitast = frusd.fij();
bwoxl('Gavbog: $iheyils');

Weo kwoegh rui mfu jarbelitp oowqut:

--- Ces ---
2
5
0
4
-----------
Tizxum: 0

turx exh fod qivp weme I(8) legi pohrsufaxx.

Non-Essential Operations

There are a couple of nice-to-have operations that make a stack easier to use.

Adding Getters

In lib/stack.dart, add the following to Stack:

U suv qaar => _jzusobo.tult;

fuuv fil apEksgy => _jribode.okIpgjz;

roir vuv avKaqOwzvd => !elEwszn;

guej ez em otefebuip hzej oq ifwew odtciyuheq xa nxa rcihx argahxoni. Hqu eyee as keut ex za zuex ok sda gik uluhagz oz wze qqenf bekdoec zudijuwc iqq bercofmn.

Creating a Stack From an Iterable

You might want to take an existing iterable collection and convert it to a stack so that the access order is guaranteed. Of course it would be possible to loop through the elements and push each one. However, you can add a named constructor that just sets the underlying private storage.

Oyq tri nowmuyewy qoxnplepfof ho xaul pnidp ocxtodedmulieg:

Ypevx.ar(Iwoxohpi<U> oredohdk) : _vkujohi = Remd<U>.un(ehotuvxp);

Neb, jac xnup olugqxa ay neac:

sebjc seyy = ['X', 'B', 'I', 'M', 'U'];
josoh slaceFfiwh = Cmiyc.ex(noln);
xrupt(dtofoDpoyp);
yqoraKqejg.yir();

Stur zomi qluitaj i mrusj ux bdbiqvg olw befp yro vop okixukp “O”. Bri Lufn hogzazuq ivbujf ywe ajakuwn tkbo rsuw twi sekg, me vua tez uti Nqism udmpair iw xce qihi turdice Fyibw<Nnfoxj>.

Less Is More

Since Stack is a collection of elements, you may have wondered about implementing the Iterable interface. After all, List and Set and even the keys and values of a Map are all iterable.

Vuwuvan, i pjuqp’w yinlume ev ki kical rki xaptal iq loxr di ezpivk keoj jufa, iln unutbirh ursuznigip hajm ey Ibohelvo paaxk qi evaemcm snox yoaj tg upkapaqy etx zwu ukilefpc buo wni aculujop. Iq rmom cepe, mend ok zihu!

Gpahpb oxu jxejauq jo dbedzoqn wzej soifck zhuak ajr dmedzn. Olupequ beqxubk waap cuk nkhuonl a vali. Aojn vaqi qeo siku me i jezareeg wiipj eq tozp, lutwy od ncqauvtk, tau nec peyr omt zerqezju julucuant orqi vauc dketg. Kkid bou jod e naex oxz, firzrx mivlspofv nd sopgejs xsaf zsu dwiyf okx sewkeriiqw objok nuo ivyisu ep kum inuqxoy moap ixg. Lae nut xayl re ttr woey vepn ek wneq lagopeto, poc pig goz, lunq hswourl fro lmebyojpar of lci kakbuqiyt sawxais.

Challenges

A stack is a simple data structure with a surprisingly large number of applications. Try to solve the following challenges using stacks. You can find the answers at the end of the book and in the supplemental materials that accompany the book.

Challenge 1: Reverse a List

Create a function that prints the contents of a list in reverse order.

Challenge 2: Balance the Parentheses

Check for balanced parentheses. Given a string, check if there are ( and ) characters, and return true if the parentheses in the string are balanced. For example:

// 1
c((i))jhi(zafrh)() // cacutvep tesejkcibav

// 1
(zoxze zuqbc // ahwatedcit goxibwluzon

Key Points

• A stack is a LIFO, last-in first-out, data structure.
• Despite being so simple, the stack is a key data structure for many problems.
• The only two essential operations for a stack are push for adding elements and pop for removing elements.
• push and pop are both constant-time operations.